/*用二叉搜索树实现unordered_map,封装成一个模板类*/
#include <iostream>
#include <algorithm>

// 二叉树的结构
template<typename K, typename V>
struct TreeNode {
    std::pair<K, V> val;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    
    TreeNode(const K& key, const V& value, TreeNode* parentNode = nullptr) : val(std::make_pair(key, value)),
        left(nullptr), right(nullptr), parent(parentNode) {}
};

// 自定义map模板类
template<typename K, typename V>
class MyMap {
private:
    TreeNode<K, V>* root;  // 根节点

    void clear(TreeNode<K, V>* node) {
        if (node == nullptr) return;
        clear(node->left);
        clear(node->right);
        delete node;
    }
public:
    MyMap() : root(nullptr) {}
    ~MyMap() { clear(); }

    // 禁止拷贝构造和拷贝赋值
    MyMap(const MyMap&) = delete;
    MyMap& operator=(const MyMap&) = delete;

    // 插入元素
    void insert(const K& key, const V& val) {
        // 创建一个节点
        TreeNode *newNode = new TreeNode(key, val, nullptr);
        if (root == nullptr) {
            root = newNode;
            return;
        }
        // 找到插入的位置
        TreeNode *p = root;
        while (p != nullptr) {
            if (key < p->val.first) {
                if (p->left == nullptr) {
                    // 左子树为空，插入到左子树
                    p->left = newNode;
                    newNode->parent = p;
                    break;
                }
                // 向左子树查找
                p = p->left;
            }
            // key大于等于当前节点的值，向右子树查找
            else if (key > p->val.first) {
                if (p->right == nullptr) {
                    // 右子树为空，插入到右子树
                    p->right = newNode;
                    newNode->parent = p;
                    break;
                }
                p = p->right;
            }
            else {  // key已经存在，更新value
                p->val.second = val;
                return;
            }
        }
    }

    // 查找元素根据key值查找，返回节点的指针(查找元素不会进行修改，所以const修饰)
    TreeNode<K,V>* find(const K& key) const {
        TreeNode<K,V>* p = root;
        while (p != nullptr) {
            if (key < p->val.first) {
                p = p->left;
            }
            else if (key > p->val.first) {
                p = p->right;
            }
            else {  // key找到
                return p;
            }
        }
        return nullptr;  // 没有找到
    }

    // 删除元素
    void remove(const K& key) {
        TreeNode<K,V>* p = find(key);
        if (p == nullptr) return;  // 没有找到

        // 找到后，分两种情况处理
        // 节点有两个子节点
        if (p->left != nullptr && p->right != nullptr) {
            // 找到后继节点
            TreeNode<K,V>* successor = p->right;
            while (successor->left != nullptr) {
                successor = successor->left;
            }
            // 用后继节点的值替换当前节点的值
            p->val = successor->val;
            // 删除后继节点
            remove(successor->val.first);
        }
        // 节点有一个或者没有节点
        TreeNode<K, V>* child = p->left != nullptr ? p->left : p->right;
        if (child != nullptr) {
            // 父节点指向子节点
            child->parent = p->parent;
        }
        if (p->parent == nullptr) {
            // 根节点
            root = child;
        } else if (p == p->parent->left) {
            // 父节点的左子节点
            p->parent->left = child;
        } else {
            // 父节点的右子节点
            p->parent->right = child;
        }
        delete p;  // 删除当前节点
    }

    // 清空map
    void clear() {
        if (root == nullptr) return;
        clear(root);
        root = nullptr;
    }
};